Chihik's Blog

An Ac a day, keeps the doctor away!

区间dp

置顶 | 发布于 2020-07-11 | 分类于 dp 、 区间dp | 19分钟 | 3285字数

一.概念

对于一段区间求最优解，且该区间可以分为几个小区间的最优解合并（最优子结构）。

二.基本思路

阅读全文 »

伯努利数

置顶 | 发布于 2020-07-11 | 分类于 数学 、 伯努利数 | 8分钟 | 1346字数

伯努利数是一个用于解决 nn 次方和的数列。

它的递归定义公式如下：

∑i=0n(n+1i)Bi=[n=0]        (1.1)\sum_{i=0}^n \binom {n+1}{i} B_i=[n=0] ~~~~~~~~ (1.1)

阅读全文 »

P6825 「EZEC-4」求和

发布于 2021-02-01 | 分类于 莫比乌斯反演 | 3分钟 | 466字数

∑i=1n∑j=1ngcd⁡(i,j)i+j\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)^{i+j}

∑d=1n∑i=1n∑j=1n[gcd⁡(i,j)=d]di+j\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]d^{i+j}

阅读全文 »

CF547C Mike and Foam

发布于 2021-02-01 | 分类于 莫比乌斯反演 | 4分钟 | 671字数

记 cic_i 为 ii 毫升泡沫的酒在架子上的瓶数，A=max⁡i=1naiA=\max_{i=1}^n a_i。

为了方便将二元组视为有序，答案除以 22 即可。

∑i=1A∑j=1Acicj[gcd⁡(i,j)=1]\sum_{i=1}^A \sum_{j=1}^A c_i c_j [\gcd(i,j)=1]

阅读全文 »

CF439E Devu and Birthday Celebration

发布于 2021-02-01 | 分类于 组合数学 、 莫比乌斯反演 | 4分钟 | 511字数

∑i1=1n∑i2=1n...∑if=1n[∑ai=n][gcd⁡ai=1]\sum_{i_1=1}^n\sum_{i_2=1}^n...\sum_{i_f=1}^n [\sum{a_i}=n][\gcd{a_i}=1]

∑i1=1n∑i2=1n...∑if=1n[∑ai=n]∑d∣gcd⁡aiμ(d)\sum_{i_1=1}^n\sum_{i_2=1}^n...\sum_{i_f=1}^n [\sum{a_i}=n]\sum_{d|\gcd{a_i}} \mu(d)

阅读全文 »
0%